Communication systems for satellite communications and mobile communications have requirements for system configurations such as reduced electric power and smaller antennas. To satisfy such requirements, an error correction coding technology has been introduced for achieving a large coding gain.
A low-density parity-check code is known as an error correcting code having a very large coding gain, and is being introduced into various communication systems and storage devices for recording data. The low-density parity-check code does not mean a particular error correction coding process, but is a collective term for error correcting codes having a sparse check matrix. A sparse check matrix is a check matrix mostly composed of 0s and having few 1s. The low-density parity-check code is characterized by a check matrix.
By selecting a sparse check matrix and using a repetitive decoding process, it is possible to realize an error correction coding process which is close to theoretical limitations and which has a very large coding gain (see Documents 1, 2). A sum-product algorithm or a min-sum algorithm may be used for such a process.
Document 4 discloses an example of a process of decoding a low-density parity-check code. A decoding device divides received data into blocks having a certain length, holds received data to be error-corrected and data called a message produced in the decoding process for each of the blocks, and corrects errors of the received data while updating the messages using a check matrix. It is assumed that one block comprises N received data (N represents an integer greater than 1). It is also assumed that the check matrix comprises elements each represented by a matrix of N rows and R columns (R represents a positive integer of N or smaller) of 0s or 1s.
If each item of the received data is expressed by b bits (b represents a positive integer), then a storage area of b×N bits is required to hold a block of N received data. Since as many messages as the number of non-zero elements of the check matrix are held, a storage area of b×(the number of non-zero elements) is required to hold messages. The non-zero elements refer to elements each having a value of 1, not 0.
The decoding process can be carried out at a high speed by holding data in RAM (random access memory) and performing parallel processing on data while simultaneously accessing a plurality of data. For performing parallel processing on increased data that can simultaneously be accessed, it is necessary to divide and record the data in a plurality of RAMs. Consequently, the decoding device needs an increased circuit scale and the process of generating addresses is complicated.
The problem regarding the number of RAMs can be solved by a method based on device configurations (see Document 5). However, such a method greatly reduces the error ratio of the decoding process. Although there is an approach to simplify the circuit arrangement by using shift registers, rather than RAMs (see Document 1), such an approach results in an increased circuit scale if the length N of a block exceeds several tens of thousands or if the number of redundant bits is large and the coding ratio is significantly small.